package com.leetcode.search.bfs;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Dennis Li
 * @date 2020/7/25 21:03
 */
public class OrangesRotting_994 {

    public int orangesRotting(int[][] grid) {
        Queue<int[]> queue = new LinkedList<>();
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int high = grid.length, width = grid[0].length;
        int oranges = 0;
        // 找到所有腐烂的橘子
        for (int i = 0; i < high; i++) {
            for (int j = 0; j < width; j++) {
                // 初始化遍历，同时记录新鲜橘子的个数以及腐烂橘子的个数
                if (grid[i][j] == 1) oranges++;
                if (grid[i][j] == 2) queue.offer(new int[]{i, j});
            }
        }
        // 没有新鲜橘子，只有烂橘子
        if (oranges == 0) return 0;
        int minute = -1;
        // 将周围的橘子入队，每次找到新鲜橘子，橘子总数减一
        // 注意oranges一定要>0，不然会多算,第一个用例就会超时
        while (oranges > 0 && !queue.isEmpty()) {
            int size = queue.size();
            minute++;
            for (int i = 0; i < size; i++) {
                int[] now = queue.poll();
                int a = now[0], b = now[1];
                if (grid[a][b] == 1) {
                    // 橘子腐烂，新鲜橘子数-1
                    grid[a][b] = 2;
                    oranges--;
                }
                for (int[] d : directions) {
                    int x = a + d[0], y = b + d[1];
                    if (x >= 0 && x < width && y >= 0 && y < high)
                        // 不能将为0的部分入队
                        if (grid[x][y] == 1) queue.offer(new int[]{x, y});
                }
            }
        }
        return oranges == 0 ? minute : -1;
    }

}
